\section{Background}

\subsection{Secret Sharing}

An $(n,t+1)$ \emph{secret sharing} scheme allows a secret $s$ to
be \emph{split} into $n$ \emph{shares}, such that any $t$ or fewer
shares reveal no information about the original secret $s$\footnote{
That is, \emph{information theoretic} security.}. However, any set
of $t+1$ shares can be used to \emph{reconstruct} the original
secret $s$. Although Shamir's construction \cite{Shamir79} using 
Lagrange Polynomial Interpolation is the most well-known
secret sharing scheme, other methods exist \cite{Ito87,Pedersen91}. 
Specifically, the
original paper by Zhou \cite{Zhou:2005:APS:1085126.1085127}
on which this work is based used the secret sharing construction
of Pedersen \cite{Pedersen91}, which is as follows:

\begin{enumerate}
\item Generate two large primes $\{p,q|p=2q+1\}$, and choose
two public elements $g,h \in \mathbb{Z}_p^*$ where $\mathbb{Z}_p^*$
has order $q$.\footnote{This scheme assumes the discrete logarithm
assumption, where no probabilistic polynomial-time algorithm can
compute $\log_gh \mod p$.}
\item Given a secret $s \in \mathbb{Z}_p$, construct an $(l,l)$
secret sharing as follows:

\begin{enumerate}
\item Choose $l-1$ random values $s_i \in \mathbb{Z}_p$
\item Choose $s_l$ such that $\Sigma_{i=1}^l s_i \mod p = s$
\end{enumerate}

\item Construct an $l$-element random vector $R$ where
$r_i \in \mathbb{Z}_q$, and make $r = \Sigma_{i=1}^l r_i \mod p$
public

\item Make public $g^s h^r \mod p, g^{s_i} h^{r_i} \mod p$ public.
These commitments are stored in the set $\Lambda$, where
$\Lambda_0 = g^s h^r \mod p, \Lambda_{i, i > 0} = g^{s_i} h^{r_i} \mod p$

\end{enumerate}

Pedersen's scheme is a \emph{non-interactive verifiable secret sharing}
construction, where verification of shares is performed as follows:

\begin{enumerate}
\item Verify sharing by computing 
$\Lambda_0 \stackrel{?}{=} \Sigma_{i=1}^n \Lambda_i \mod p$
\item Verify private share $s_i$ by computing 
$\Lambda_i \stackrel{?}{=} g^{s_i} h^{r_i} \mod p$
using the public parameters $\langle g,h, \Lambda \rangle$
\end{enumerate}

Shares are distributed to servers by constructing ${{n}\choose{t}}$
unique server sets. As each share is distributed to $t$ servers and
each server set is unique, no set of $t$ servers can collude to recover
the original secret. This share distribution scheme was proposed
by Ito \cite{Ito87}. The full algorithm is described in Figure \ref{alg}.

\begin{center}
\begin{figure}[here]
\resizebox{!}{12 cm}{\includegraphics{img/VSS.png}}
\caption{Verifiable Secret Sharing Scheme}
\label{alg}
\end{figure}
\end{center}

\subsection{Subsharings}

The process of \emph{share refreshing} is accomplished by repeatedly
applying Pedersen's secret splitting scheme to the shares themselves.
That is, each server originally receives a set of shares $S_i$ from the dealer.
In each round of share refreshing, servers generate a secret sharing for
all shares $s_i \in S_i$. Clearly this results in an \emph{exponential} expansion
in the number of shares that must be maintained. We discuss the implications of this in Section \ref{con}.


% ---- Implementation 
%\subsection{Hybrid Cryptosystem}

%In order to distribute shares among servers, the identity of the
%sender must be verifiable, and the secret share $s_i$ and associated
%random value $r_i$ must remain private from eavesdropping servers.
%To accomplish this, all messages are signed by first hashing the message
%with SHA-1, and signing the hash with the sender's private RSA \cite{RSA} 
%key.\\ \indent
%As the messages are larger than the RSA modulus, we first generate an
%ephemeral AES key. This symmetric key is used to encrypt the message,
%and the symmetric key is then encrypted using the receiver's public RSA
%key.


\subsection{Asynchronous Communication}

The secret sharing scheme assumes the communication between servers to be 
asynchronous. Furthermore an adversary may compromise up to $t$ servers during a 
time window of $T$. The compromised servers will display byzantine behavior  
when they are compromised and the adversary will be able to obtain the set of 
shares associated with those servers.Therefore a server will only wait for 
$n - t$ other servers' messages to arrive before making progress.


Furthermore, the compromised servers may never send messages in during share 
refreshing or their incorrect messages may reach a correct server before messages 
from other correct servers. Therefore only $(n - t) - t = n - 2t$ servers are 
guaranteed to participate correctly.

At this point for as long as $n - 2t \ge t + 1$ any of the correct servers will 
be able to make progress. This is because, for example to reconstruct the 
original secret, if correct subshares from at least $t + 1$ correct servers was 
not received, then reconstruction will fail (due to $(n, t+1)$ sharing scheme).

Therefore this constraint provides the minimum number of participant servers
in the system : $n \ge 3t + 1$





